#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<list>
#include<algorithm>
using namespace std;

void test_list1()
{
	list<int> lt;
	//push_back
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);
	//迭代器访问
	list<int>::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << ' ';
		it++;
	}
	cout << endl;
	for (auto& e : lt)
	{
		cout << e << ' ';
	}
	cout << endl;
	it = lt.begin();
	while (it != lt.end())
	{
		*it *= 2;
		it++;
	}
	for (auto& e : lt)
	{
		cout << e << ' ';
	}
	cout << endl;
	//头插push_front
	lt.push_front(10);
	lt.push_front(20);
	lt.push_front(30);
	lt.push_front(40);
	//尾删pop_back
	lt.pop_back();
	lt.pop_back();
	for (auto& e : lt)
	{
		cout << e << ' ';
	}
	cout << endl;
	//insert
	list<int>::iterator pos = find(lt.begin(), lt.end(), 6);
	if (pos != lt.end())
	{
		//pos不会失效
		lt.insert(pos, 50);
		*pos *= 10;
	}
	for (auto& e : lt)
	{
		cout << e << ' ';
	}
	cout << endl;
	//erase
	pos = find(lt.begin(), lt.end(), 8);
	if (pos != lt.end())
	{
		//pos会失效
		lt.erase(pos);
		//已经失效了,erase后，pos指向空间已被释放，再访问*pos野指针问题。
		//cout << *pos << endl;该平台下没报错

	}
	for (auto& e : lt)
	{
		cout << e << ' ';
	}
	cout << endl;
}

void test_list2()
{
	//splice转移函数	void splice(iterator pos,list& rlt)	;rlt转移给lt的pos位置前
	list<int>lt;
	list<int>rlt;
	for (int i = 1; i < 5; i++)
	{
		lt.push_back(i);
		rlt.push_back(i);
	}
	cout << "初始lt链表:";
	for (auto& e : lt)
	{
		cout << e << ' ';

	}
	cout << endl;
	cout << "初始rlt链表:";
	for (auto& e : rlt)
	{
		cout << e << ' ';

	}
	cout << endl;

	list<int>::iterator pos = find(lt.begin(), lt.end(), 3);
	lt.splice(pos, rlt);
	cout << "转移后lt链表:";
	for (auto& e : lt)
	{
		cout << e << ' ';

	}
	cout << endl;
	cout << "转移后rlt链表:";
	for (auto& e : rlt)
	{
		cout << e << ' ';

	}
	cout << endl;
	//remove函数	void remove(const value_type& val);	把链表中的val元素全部删除
	lt.remove(1);
	cout << "删除1后lt链表:";
	for (auto& e : lt)
	{
		cout << e << ' ';

	}
	cout << endl;

	//unique	去重，前提：必须有序sort;基本不用，因为sort排序代价太大

	//reverse	逆置

	//sort	链表的sort函数，不是标准库的，因为空间不是连续的;链表排序选用归并排序,不需要要再额外开空间
			//快排和归并时间复杂度O（nlogn)
}
//N个数据排序，是选择vector+算法sort？还是list+ sort?

void test_list3()
{
	list<int>lt1;
	list<int>lt2;
	lt1.push_back(1);
	lt1.push_back(2);
	lt2.push_back(3);
	lt2.push_back(4);

	//merge	归并
	
	lt1.merge(lt2);

	cout << "归并后lt1:";
	for (auto& e : lt1)
	{
		cout << e << ' ';
	}
	cout << endl;
	cout << "归并后lt2:";
	for (auto& e : lt2)
	{
		cout << e << ' ';
	}
	cout << endl;
}

int main()
{
	test_list3();
	return 0;
}